/* WUGraph.java */

package graph;

import java.util.Hashtable;

import list.AdjacencyList;
import list.AdjacencyListNode;
import list.DList;
import list.DListNode;
import list.InvalidNodeException;

/**
 * The WUGraph class represents a weighted, undirected graph. Self-edges are
 * permitted.
 */

public class WUGraph {
	
	/**
	 * Fields
	 */
	
	private int numOfVertices;
	private int numOfEdges;
	private Hashtable<Object, DListNode> vertexHashtable;
	private Hashtable<VertexPair, AdjacencyListNode> edgeHashtable;
	//This is a DList of AdjacencyLists
	private DList vertexList;
	

	/**
	 * WUGraph() constructs a graph having no vertices or edges.
	 * 
	 * Running time: O(1).
	 */
	public WUGraph() {
		numOfVertices = 0;
		numOfEdges = 0;
		vertexHashtable = new Hashtable<Object, DListNode>();
		edgeHashtable = new Hashtable<VertexPair, AdjacencyListNode>();
		vertexList = new DList();
	}

	/**
	 * vertexCount() returns the number of vertices in the graph.
	 * 
	 * Running time: O(1).
	 */
	public int vertexCount() {
		return numOfVertices;
	}

	/**
	 * edgeCount() returns the number of edges in the graph.
	 * 
	 * Running time: O(1).
	 */
	public int edgeCount() {
		return numOfEdges;
	}

	/**
	 * getVertices() returns an array containing all the objects that serve as
	 * vertices of the graph. The array's length is exactly equal to the number
	 * of vertices. If the graph has no vertices, the array has length zero.
	 * 
	 * (NOTE: Do not return any internal data structure you use to represent
	 * vertices! Return only the same objects that were provided by the calling
	 * application in calls to addVertex().)
	 * 
	 * Running time: O(|V|).
	 */
	public Object[] getVertices() {
		Object[] arrayOfVertices = new Object[numOfVertices];
		if (numOfVertices > 0) {
			DListNode node = (DListNode) vertexList.front();
			for (int i = 0; i < numOfVertices; i++) {
				try {
					arrayOfVertices[i] = ((VertexAndEdges)node.item()).vertex;
					node = (DListNode) node.next();
				} catch (InvalidNodeException e) {
					e.printStackTrace();
				}
			}
		}
		return arrayOfVertices;
	}

	/**
	 * addVertex() adds a vertex (with no incident edges) to the graph. The
	 * vertex's "name" is the object provided as the parameter "vertex". If this
	 * object is already a vertex of the graph, the graph is unchanged.
	 * 
	 * Running time: O(1).
	 */
	public void addVertex(Object vertex) {
		if (!isVertex(vertex)) {
			AdjacencyList adjList = new AdjacencyList();
			VertexAndEdges vertAndEdge = new VertexAndEdges(vertex, adjList);
			vertexList.insertFront(vertAndEdge);
			DListNode node = (DListNode) vertexList.front();
			vertexHashtable.put(vertex, node);
			numOfVertices++;
		}
	}

	/**
	 * removeVertex() removes a vertex from the graph. All edges incident on the
	 * deleted vertex are removed as well. If the parameter "vertex" does not
	 * represent a vertex of the graph, the graph is unchanged.
	 * 
	 * Running time: O(d), where d is the degree of "vertex".
	 */
	
	public void removeVertex(Object vertex) {
		if (isVertex(vertex)) {
			DListNode node = (DListNode) vertexHashtable.get(vertex);
			try {
				AdjacencyList edgeList = getAdjList(vertex);
				AdjacencyListNode anode = (AdjacencyListNode) edgeList.front();
				while (anode.isValidNode()){
					VertexPair vp = (VertexPair) anode.item();
					anode = (AdjacencyListNode) anode.next();
					removeEdge(vp.object1, vp.object2);
				}
				node.remove();
				vertexHashtable.remove(vertex);
				numOfVertices--;
			} catch (InvalidNodeException e) {
				e.printStackTrace();
			}
		}
	}

	/**
	 * isVertex() returns true if the parameter "vertex" represents a vertex of
	 * the graph.
	 * 
	 * Running time: O(1).
	 */
	public boolean isVertex(Object vertex) {
		return vertexHashtable.containsKey(vertex);
	}

	/**
	 * degree() returns the degree of a vertex. Self-edges add only one to the
	 * degree of a vertex. If the parameter "vertex" doesn't represent a vertex
	 * of the graph, zero is returned.
	 * 
	 * Running time: O(1).
	 */
	 
	public int degree(Object vertex) {
		if (isVertex(vertex)) {
			AdjacencyList v;
			try {
				v = ((VertexAndEdges)((DListNode)vertexHashtable.get(vertex)).item()).edges;
				return v.getDegree();
			} catch (InvalidNodeException e) {
				e.printStackTrace();
			}
			return 0;
		} else {
			return 0;
		}
	}

	/**
	 * getNeighbors() returns a new Neighbors object referencing two arrays. The
	 * Neighbors.neighborList array contains each object that is connected to
	 * the input object by an edge. The Neighbors.weightList array contains the
	 * weights of the corresponding edges. The length of both arrays is equal to
	 * the number of edges incident on the input vertex. If the vertex has
	 * degree zero, or if the parameter "vertex" does not represent a vertex of
	 * the graph, null is returned (instead of a Neighbors object).
	 * 
	 * The returned Neighbors object, and the two arrays, are both newly
	 * created. No previously existing Neighbors object or array is changed.
	 * 
	 * (NOTE: In the neighborList array, do not return any internal data
	 * structure you use to represent vertices! Return only the same objects
	 * that were provided by the calling application in calls to addVertex().)
	 * 
	 * Running time: O(d), where d is the degree of "vertex".
	 */
	public Neighbors getNeighbors(Object vertex) {
		if (isVertex(vertex)) {
			VertexAndEdges container;
			try {
				container = (VertexAndEdges)((DListNode)vertexHashtable.get(vertex)).item();
				AdjacencyList adjList = container.edges;
				if (adjList.getDegree() > 0) {
					Object[] neighborList = new Object[adjList.getDegree()];
					int[] weightList = new int[adjList.getDegree()];
					AdjacencyListNode node = (AdjacencyListNode) adjList.front();
					for (int i = 0; i < adjList.getDegree(); i++) {
						Object obj = ((VertexPair)node.item()).object1;
						if (obj == vertex) {
							obj = ((VertexPair)node.item()).object2;
						}
						neighborList[i] = obj;
						weightList[i] = ((VertexPair)node.item()).weight;
						node = (AdjacencyListNode) node.next();
					}
					Neighbors neighbor = new Neighbors();
					neighbor.neighborList = neighborList;
					neighbor.weightList = weightList;
					return neighbor;
				}
			} catch (InvalidNodeException e1) {
				e1.printStackTrace();
			}
			
		}
		return null;
	}

	/**
	 * addEdge() adds an edge (u, v) to the graph. If either of the parameters u
	 * and v does not represent a vertex of the graph, the graph is unchanged.
	 * The edge is assigned a weight of "weight". If the edge is already
	 * contained in the graph, the weight is updated to reflect the new value.
	 * Self-edges (where u == v) are allowed.
	 * 
	 * Running time: O(1).
	 */
	public void addEdge(Object u, Object v, int weight) {
		VertexPair vp = new VertexPair(u, v, weight);
		if (!isVertex(u) || !isVertex(v)) {
			// do nothing
		} else if (isEdge(u, v)) {
			AdjacencyListNode adjNode = (AdjacencyListNode) edgeHashtable.get(vp);
			VertexPair realVP;
			try {
				realVP = (VertexPair) adjNode.item();
				realVP.weight = weight;
			} catch (InvalidNodeException e) {
				e.printStackTrace();
			}
		} else if (u.equals(v)) {
			AdjacencyList list1 = getAdjList(u);
			list1.insertFront(vp);
			AdjacencyListNode twin = (AdjacencyListNode)list1.front();
			twin.setPartner((AdjacencyListNode)list1.front());
			edgeHashtable.put(vp, twin);
			list1.setDegree(list1.getDegree() + 1);
			numOfEdges++;
		} else {
			AdjacencyList list1 = getAdjList(u);
			AdjacencyList list2 = getAdjList(v);
			list1.insertFront(vp);
			list2.insertFront(vp);
			AdjacencyListNode twin = (AdjacencyListNode)list2.front();
			twin.setPartner((AdjacencyListNode)list1.front());
			edgeHashtable.put(vp, twin);
			list1.setDegree(list1.getDegree() + 1);
			list2.setDegree(list2.getDegree() + 1);
			numOfEdges++;
		}
	}
	
	/**
	 * Gets the AdjacencyList of edges with the given vertex.
	 * @param u is the vertex object that is passed into the method
	 * @return the AdjacencyList with the given vertex
	 */
	private AdjacencyList getAdjList(Object u) {
		if (isVertex(u)) {
			try {
				return (AdjacencyList)((VertexAndEdges)((DListNode)vertexHashtable.get(u)).item()).edges;
			} catch (InvalidNodeException e) {
				e.printStackTrace();
			}
			return null;
		} else {
			return null;
		}
	}

	/**
	 * removeEdge() removes an edge (u, v) from the graph. If either of the
	 * parameters u and v does not represent a vertex of the graph, the graph is
	 * unchanged. If (u, v) is not an edge of the graph, the graph is unchanged.
	 * 
	 * Running time: O(1).
	 */
	
	public void removeEdge(Object u, Object v) {
		if (isEdge(u, v)) {
			VertexPair vp = new VertexPair(u, v);
			AdjacencyListNode node = (AdjacencyListNode) edgeHashtable.get(vp);
			AdjacencyListNode partner = node.getPartner();
			AdjacencyList nodeList = node.getList();
			AdjacencyList partnerList = partner.getList();
			nodeList.setDegree(nodeList.getDegree()-1);
			if (!u.equals(v)) {
				partnerList.setDegree(partnerList.getDegree()-1);
			}
			try {
				node.remove();
				if (!u.equals(v)) {
					partner.remove();
				}
			} catch (InvalidNodeException e) {
				e.printStackTrace();
			}
			edgeHashtable.remove(vp);
			numOfEdges--;			
		}
	}

	/**
	 * isEdge() returns true if (u, v) is an edge of the graph. Returns false if
	 * (u, v) is not an edge (including the case where either of the parameters
	 * u and v does not represent a vertex of the graph).
	 * 
	 * Running time: O(1).
	 */
	public boolean isEdge(Object u, Object v) {
		VertexPair vp = new VertexPair(u, v);
		return edgeHashtable.containsKey(vp);
	}

	/**
	 * weight() returns the weight of (u, v). Returns zero if (u, v) is not an
	 * edge (including the case where either of the parameters u and v does not
	 * represent a vertex of the graph).
	 * 
	 * (NOTE: A well-behaved application should try to avoid calling this method
	 * for an edge that is not in the graph, and should certainly not treat the
	 * result as if it actually represents an edge with weight zero. However,
	 * some sort of default response is necessary for missing edges, so we
	 * return zero. An exception would be more appropriate, but also more
	 * annoying.)
	 * 
	 * Running time: O(1).
	 */
	
	public int weight(Object u, Object v) {
		if (isEdge(u, v)) {
			AdjacencyListNode node = (AdjacencyListNode) edgeHashtable.get(new VertexPair(u, v));
			VertexPair vp;
			try {
				vp = (VertexPair) node.item();
				return vp.weight;
			} catch (InvalidNodeException e) {
				e.printStackTrace();
			}
			return 0;
		} else {
		return 0;
		}
	}

}
